#pragma once

// Left inclusive, right exclusive.
template<class T>
void QuickSortAscend(T arr[], int32 left, int32 right) {
	int32 i = left, j = right;
	T pivot = arr[(left + right) / 2];

	while (i <= j) {
		while (arr[i] < pivot) {
			i++;
		}
		while (arr[j] > pivot) {
			j--;
		}
		if (i <= j) {
			T temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}

	if (left < j) {
		QuickSortAscend(arr, left, j);
	}
	if (i < right) {
		QuickSortAscend(arr, i, right);
	}
};

// Left inclusive, right inclusive.
template<class T>
void QuickSortDescend(T arr[], int32 left, int32 right) {
	int32 i = left, j = right;
	T pivot = arr[(left + right) / 2];

	while (i <= j) {
		while (arr[i] > pivot) {
			i++;
		}
		while (arr[j] < pivot) {
			j--;
		}
		if (i <= j) {
			T temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}

	if (left > j) {
		QuickSortDescend(arr, left, j);
	}
	if (i > right) {
		QuickSortDescend(arr, i, right);
	}
};

template<class _key, class _data>
struct OpenMap
{
public:
	_key* key;
	_data* data;

	uint32 size;
	uint32 capacity;

	OpenMap()
	{
		data = new _data[1];
		key = new _key[1];

		size = 0;
		capacity = 1;
	}

	~OpenMap()
	{
		if (capacity) {
			delete[] key;
			delete[] data;
		}

		key = NULL;
		data = NULL;
	}

	inline _data& operator[](const _key key_lookup) const
	{
		return data[Index(key_lookup)];
	}

	inline uint32 Index(_key find_key) const
	{
		// To start, find the subscript of the middle position.
		uint32 lowerbound = 0, upperbound = size;
		uint32 position = (lowerbound + upperbound) / 2;

		while ((key[position] != find_key) && (lowerbound <= upperbound))
		{
			if (key[position] > find_key) {		// If the number is > key, ..
				upperbound = position - 1;		// decrease position by one.
			} else {							// Else, increase position by one.                       
				lowerbound = position + 1;
			}
			position = (lowerbound + upperbound) / 2;
		}

		return position;
	}


	void Insert(_key set_key, _data set_data)
	{
		if (size == capacity) {
			capacity *= 2;

			_data* temp_data = data;
			data = new _data[capacity];
			memcpy(data, temp_data, size * sizeof(_data));
			delete[] temp_data;

			_key* temp_key = key;
			key = new _key[capacity];
			memcpy(key, temp_key, size * sizeof(_key));
			delete[] temp_key;
		}

		// find the index to insert into. Remember the keys are ordered ascending.
		uint32 idx = 0;
		while (idx < size && set_key > key[idx]) {
			idx++;
		}

		// shift all the elements over to make room.
		for (uint32 i = size; i > idx; i--) {
			key[i] = key[i - 1];
			data[i] = data[i - 1];
		}

		key[idx] = set_key;
		data[idx] = set_data;
		size++;
	}

	void Remove(_key remove_key)
	{
		for (uint32 i = Index(remove_key) + 1; i < size; i++) {
			// Shift the data to the previous cell. 
			key[i - 1] = key[i];
			data[i - 1] = data[i];
		}
		size--;
	}

	void Remove(const _key* const remove_keys, const uint32 count)
	{
		_key* sorted_keys = new _key[count];
		memcpy(sorted_keys, remove_keys, count * sizeof(_key));
		QuickSortAscend(sorted_keys, 0, count);

		RemoveSorted(sorted_keys, count);
		delete[] sorted_keys;
	}

	void RemoveSorted(const _key* const remove_keys, const uint32 count)
	{
		uint32 defunct_idx = 1;
		for (uint32 i = Index(remove_keys[0]) + 1; i < size; i++) {
			if (key[i] != remove_keys[defunct_idx]) {
				// Shift the data to the previous cell. 
				// Note that logically we must atleast start at index 1 (not 0) and if we are already at the end then the for loop quites before 1 iteration.
				key[i - defunct_idx] = key[i];
				data[i - defunct_idx] = data[i];
			}
			else {
				// If it is increase the shift count and move on to the next index.
				defunct_idx++;
			}
		}
		size -= count;
	}

	void Clear()
	{
		if (capacity) {
			delete[] key;
			delete[] data;
		}

		key = NULL;
		data = NULL;
		size = 0;
		capacity = 0;
	}

};

template<class T>
struct OpenVector
{
public:
	T* data;

	uint32 size;
	uint32 allocated; // change to capacity

	OpenVector()
	{
		data = new T[1];

		size = 0;
		allocated = 1;
	}

	~OpenVector()
	{
		if (allocated) {
			delete[] data;
		}
		data = NULL;
	}


	void Add(const T& newData)
	{
		// Check to see if the array needs to be res-size.
		if (size == allocated) {
			allocated *= 2;

			T* new_data = data;
			data = new T[allocated];
			memcpy(data, new_data, size * sizeof(T));
			delete[] new_data;
		}

		data[size++] = newData;
	}

	void Remove(const uint32 index)
	{
		for (uint32 i = index; i < size i++) {
			data[i] = data[i + 1];
		}
	}

	void Clear()
	{
		if (allocated) {
			delete[] data;
		}

		data = NULL;
		size = 0;
		allocated = 0;
	}
};